【链表问题】打卡7：将单向链表按某值划分成左边小，中间相等，右边大的形式

前言

以专题的形式更新刷题贴，欢迎跟我一起学习刷题，相信我，你的坚持，绝对会有意想不到的收获。每道题会提供简单的解答，如果你有更优雅的做法，欢迎提供指点，谢谢。

注：如果代码排版出现了问题麻烦通知我下，谢谢。

【题目描述】

给定一个单向链表的头结点head,节点的值类型是整型，再给定一个整数privot。实现一个调整链表的函数，将链表调整为左部分都是值小于privot的节点，中间部分都是值等于privot的节点，右部分都是大于privot的节点。且对某部分内部节点的顺序不做要求

例如:链表9-0-4-5-1，pivot=3。

调整后是1-0-4-9-5，

也可以是0-1-9-5-4

【要求】

如果链表的长度为 N, 时间复杂度达到 O(N)。

【难度】

尉：★★☆☆

【解答】

这道题在思路上还是比较简单的，但是在实现上还是有一些细节需要主要的。

本题对某部分的内部节点不做要求，一种很简单的方法就是用一个数组来存链表的节点，然后像类似于快速排序的分割函数那样，按照某个值把他们进行划分。

不过这样做的话，空间复杂度为 O(N)。我们也可以采取使用3个指针，把原链表依次划分成三个部分的链表，然后再把他们合并起来，这种做法不但空间复杂度为 O(1), 而且内部节点的顺序也是和原链表一样的。虽然思路简单，但在代码实现上也是有很多细节需要注意的，有时间的话希望大家动手打下码。

代码如下

 1//用三个指针处理，这道题主要是要注意串联链表时的一些细节处理
 2public static Node listPartition(Node head, int pivot) {
 3    Node sB = null;//小的指针头，即small begin
 4    Node sE = null;//小的指针尾，即 small end
 5    Node eB = null;//中的指针头，即 equal begin
 6    Node eE = null;//中的指针尾，即emall end
 7    Node bB = null;//大的指针头，即 big begin
 8    Node bE = null;//大的指针尾，即 big end
 9    Node next = null;//保存下一个节点
10    //进行划分
11    while (head != null) {
12        next = head.next;
13        head.next = null;
14        if (head.value < pivot) {
15            if (sB == null) {
16                sB = head;
17                sE = head;
18            } else {
19                sE.next = head;
20                sE = sE.next;
21            }
22        } else if (head.value == pivot) {
23            if (eB == null) {
24                eB = head;
25                eE = head;
26            } else {
27                eE.next = head;
28                eE = eE.next;
29            }
30        } else {
31            if (bB == null) {
32                bB = head;
33                bE = head;
34            } else {
35                bE.next = head;
36                bE = bE.next;
37            }
38        }
39        head = next;
40    }
41    //把三部分串连起来，串联的时候细节还是挺多的，
42    //串联的过程下面代码的精简程度是最学习的部分了
43
44    //1.小的与中的串联
45    if (sB != null) {
46        sE.next = eB;
47        eE = eE == null ? sE : eE;
48    }
49    //2.中的和大的连接
50    if (eB != null) {
51        eE.next = bB;
52    }
53    return sB != null ? sB : eB != null ? eB : bB;
54}

问题拓展

思考：如果给你的是一个环形链表，让你来划分，又该如何实现呢？

【题目描述】

无

【要求】

无

【难度】

未知。

【解答】

无。

往期